package mao.leetcode.offer;

import java.util.stream.IntStream;

/**
 * @author Totoro
 * @date 2020/8/15
 * @explain:
 */
public class offer66 {

    class Solution1 {
        public int maxProfit(int[] prices) {
            if (prices.length == 1) return 0;
            int n = prices.length;
            //表示从当前开始，右边最大的值
            int[] dp = new int[prices.length];
            for(int i=n-2;i>=0;i--){
                //从右向左开始更新dp的值
                dp[i] = Math.max(prices[i+1],dp[i+1]);
            }

            int max = 0;
            for(int i=0;i<n;i++){
                max = Math.max(max,dp[i]-prices[i]);
            }
            return max;

            //IntStream.range()
        }
    }
}
